home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / agrep / utilities.c < prev   
C/C++ Source or Header  |  1994-08-01  |  3KB  |  139 lines
  1. /* this file contains various utility functions for accessing
  2.    and manipulating regular expression syntax trees.    */
  3.  
  4. #include <stdio.h>
  5. #include "re.h"
  6.  
  7. /************************************************************************/
  8. /*                                                                      */
  9. /*  the following routines implement an abstract data type "stack".    */
  10. /*                                                                      */
  11. /************************************************************************/
  12.  
  13. Stack Push(s, v)
  14. Stack *s;
  15. Re_node v;
  16. {
  17.     Stack node;
  18.  
  19.     node = (Stack) new_node(node);
  20.     if (s == NULL || node == NULL) return NULL;        /* can't allocate */
  21.     node->next = *s;
  22.     node->val = v;
  23.     if (*s == NULL) node->size = 1;
  24.     else node->size = (*s)->size + 1;
  25.     *s = node;
  26.     return *s;
  27. }
  28.  
  29. Re_node Pop(s)
  30. Stack *s;
  31. {
  32.     Re_node node;
  33.     Stack temp;
  34.  
  35.     if (s == NULL || *s == NULL) return NULL;
  36.     else {
  37.     temp = *s;
  38.     node = (*s)->val;
  39.     *s = (*s)->next;
  40.     free(temp);
  41.     return node;
  42.     }
  43. }
  44.  
  45. Re_node Top(s)
  46. Stack s;
  47. {
  48.     if (s == NULL) return NULL;
  49.     else return s->val;
  50. }
  51.  
  52. int Size(s)
  53. Stack s;
  54. {
  55.     if (s == NULL) return 0;
  56.     else return s->size;
  57. }
  58.  
  59. /************************************************************************/
  60. /*                                                                      */
  61. /*    the following routines manipulate sets of positions.        */
  62. /*                                                                      */
  63. /************************************************************************/
  64.  
  65. int occurs_in(n, p)
  66. int n;
  67. Pset p;
  68. {
  69.     while (p != NULL)
  70.     if (n == p->posnum) return 1;
  71.     else p = p->nextpos;
  72.     return 0;
  73. }
  74.  
  75. /* pset_union() takes two position-sets and returns their union.    */
  76.  
  77. Pset pset_union(s1, s2)
  78. Pset s1, s2;
  79. {
  80.     Pset hd, curr, new;
  81.     int occ;
  82.  
  83.     hd = NULL; curr = NULL;
  84.     while (s1 != NULL) {
  85.     if (!occurs_in(s1->posnum, s2)) {
  86.         new = (Pset) new_node(new);
  87.         if (new == NULL) return NULL;
  88.         new->posnum = s1->posnum;
  89.         if (hd == NULL) hd = new;
  90.         else curr->nextpos = new;
  91.     }
  92.     curr = new;
  93.     s1 = s1->nextpos;
  94.     }
  95.     if (hd == NULL) hd = s2;
  96.     else curr->nextpos = s2;
  97.     return hd;
  98. }
  99.  
  100. /* create_pos() creates a position node with the position value given,
  101.    then returns a pointer to this node.                    */
  102.  
  103. Pset create_pos(n)
  104. int n;
  105. {
  106.     Pset x;
  107.  
  108.     x = (Pset) new_node(x);
  109.     if (x == NULL) return NULL;
  110.     x->posnum = n;
  111.     x->nextpos = NULL;
  112.     return x;
  113. }
  114.  
  115. /* eq_pset() takes two position sets and checks to see if they are
  116.    equal.  It returns 1 if the sets are equal, 0 if they are not.    */
  117.  
  118. subset_pset(s1, s2)
  119. Pset s1, s2;
  120. {
  121.     int subs = 1;
  122.  
  123.     while (s1 != NULL && subs != 0) {
  124.     subs = 0;
  125.     while (s2 != NULL && subs != 1)
  126.         if (s1->posnum == s2->posnum) subs = 1;
  127.         else s2 = s2->nextpos;
  128.     s1 = s1->nextpos;
  129.     }
  130.     return subs;
  131. }    
  132.  
  133. int eq_pset(s1, s2)
  134. Pset s1, s2;
  135. {
  136.     return subset_pset(s1, s2) && subset_pset(s2, s1);
  137. }
  138.  
  139.